package com.neusoft.tree.avl;

import com.neusoft.tree.Node;

import java.util.Objects;

/**
 * @author lichunlong lcl253137@alibaba-inc.com
 * @desc AVL树节点类
 * @date 2025-04-15
 */
public class AvlTreeNode extends Node<Integer> {

    public AvlTreeNode(Integer item) {
        super(item);
    }

    /**
     * 添加AVL树节点
     *
     * @param node AVL树节点
     */
    public void add(AvlTreeNode node) {
        if (Objects.isNull(node)) {
            return;
        }

        if (node.getItem() < this.getItem()) {
            if (Objects.isNull(this.getSubLeft())) {
                this.setSubLeft(node);
            } else {
                // 递归向左子树添加
                AvlTreeNode subLeft = (AvlTreeNode) this.getSubLeft();
                subLeft.add(node);
            }
        } else {
            if (Objects.isNull(this.getSubRight())) {
                this.setSubRight(node);
            } else {
                // 递归向右子树添加
                AvlTreeNode subRight = (AvlTreeNode) this.getSubRight();
                subRight.add(node);
            }
        }

        // 当添加完一个结点后，右子树的高度-左子树的高度>1 => 左旋
        if (getSubRightTreeDepth() - getSubLeftTreeDepth() > 1) {
            // 如果右子树的【左子树】高度大于右子树的【右子树】高度: 先对右子树进行右旋, 再对当前结点进行左旋
            AvlTreeNode subRightNode = (AvlTreeNode) this.getSubRight();
            if (Objects.nonNull(subRightNode) && subRightNode.getSubLeftTreeDepth() > subRightNode.getSubRightTreeDepth()) {
                // 1、先对右子树进行右旋
                subRightNode.dextrorotation();
            }
            // 2、再对当前结点进行左旋
            levorotation();

            // 左旋与右旋操作互斥, 不能同时执行
            return;
        }

        // 当添加完一个结点后，左子树的高度-右树的高度>1 => 右旋
        if (getSubLeftTreeDepth() - getSubRightTreeDepth() > 1) {
            // 如果左子树的【右子树】高度大于左子树的【左子树】高度: 先对左子树进行左旋, 再对当前结点进行右旋
            AvlTreeNode subLeftNode = (AvlTreeNode) this.getSubLeft();
            if (Objects.nonNull(subLeftNode) && subLeftNode.getSubRightTreeDepth() > subLeftNode.getSubLeftTreeDepth()) {
                // 1、先对左子树进行左旋
                subLeftNode.levorotation();
            }
            // 2、再对当前结点进行右旋
            dextrorotation();
        }
    }

    /**
     * 获取树的高度
     *
     * @return 树的高度
     */
    public int getTreeDepth() {
        return Math.max(Objects.isNull(this.getSubLeft()) ? 0 : ((AvlTreeNode) this.getSubLeft()).getTreeDepth(), Objects.isNull(this.getSubRight()) ? 0 : ((AvlTreeNode) this.getSubRight()).getTreeDepth()) + 1;
    }

    /**
     * 获取左子树的高度
     *
     * @return 左子树的高度
     */
    public int getSubLeftTreeDepth() {
        return Objects.isNull(this.getSubLeft()) ? 0 : ((AvlTreeNode) this.getSubLeft()).getTreeDepth();
    }

    /**
     * 获取右子树的高度
     *
     * @return 右子树的高度
     */
    public int getSubRightTreeDepth() {
        return Objects.isNull(this.getSubRight()) ? 0 : ((AvlTreeNode) this.getSubRight()).getTreeDepth();
    }

    /**
     * AVL树左旋6步骤
     */
    public void levorotation() {
        // 1、创建新结点，赋以当前根结点的值
        AvlTreeNode newNode = new AvlTreeNode(this.getItem());
        // 2、把新结点的左子树设置成当前结点的左子树
        newNode.setSubLeft(this.getSubLeft());
        // 3、把新结点的右子树设置成当前结点的右子树的左子树
        newNode.setSubRight(this.getSubRight().getSubLeft());
        // 4、把当前结点的值替换成右子结点的值
        this.setItem(this.getSubRight().getItem());
        // 5、把当前结点的右子树设置成当前结点右子树的右子树
        this.setSubRight(this.getSubRight().getSubRight());
        // 6、把当前结点的左子树(左子结点)设置成新的结点
        this.setSubLeft(newNode);
    }

    /**
     * AVL树右旋6步骤
     */
    public void dextrorotation() {
        // 1、创建新结点，赋以当前根结点的值
        AvlTreeNode newNode = new AvlTreeNode(this.getItem());
        // 2、把新结点的右子树设置成当前结点的右子树
        newNode.setSubRight(this.getSubRight());
        // 3、把新结点的左子树设置成当前结点的左子树的右子树
        newNode.setSubLeft(this.getSubLeft().getSubRight());
        // 4、把当前结点的值替换成左子结点的值
        this.setItem(this.getSubLeft().getItem());
        // 5、把当前结点的左子树设置成当前结点左子树的左子树
        this.setSubLeft(this.getSubLeft().getSubLeft());
        // 6、把当前结点的左子树(左子结点)设置成新的结点
        this.setSubRight(newNode);
    }

}
